package com.hello;

 /**快速排序【升序】
  * 适合大量数据做排序
 算法步骤：
 1、选定一个基准数arr[start]
 2、选定两个标兵left、right
 3、right标兵从右向左移动，遇到比基准数小的数则停下来
 4、left标兵从左向右移动，遇到比基准数大的数则停下来
 5、交换right和left数
 6、若left和right重合，则把重合数与基准数进行交换
 7、一轮结束，基准数在中间
 8、对基准数左右两边的数组重复上述步骤，直至left和right重合。
 备注:如果想倒序，则修改步骤3、4

 时间复杂度：
 一、最好情况：每次划分均匀
 1   n
 2   n + 2*1/2n=2n
 3   n + 2+1/2n + 4*1/4n = 3n
 k   kn
 又因为
 n = 2^k
 k = logn
 所以
k   nlogn

 二、当待排序的序列为正序或逆序排列时，且每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。
 1  n
 2  n+(n - 1)
 3  n+(n-1)+(n-2)
 n  n+(n-1)+(n-2)...+1 = n(n-1)/2=n^2
  */

public class FastSort {

    public static void main(String[] args) {
        int[] arr = {6, 2, 4, 6, 7, 8, 9, 2, 3, 4, 1};
        fastSort(arr, 0, arr.length - 1);
        for (int a : arr) {
            System.out.print(","+a);
        }
    }

    public static void fastSort(int[] arr, int start,int end){

        // 开始索引大于等于结束索引则停止排序
        if (start >= end) {
            return;
        }

        // 1、选定一个基准数arr[start]
        int flag = arr[start];
        // 2、选定两个标兵left、right
        int left = start;
        int right = end;

        // 当两位标兵未重合则继续探索
        while (left < right) {
            // 3、right标兵从右向左移动，遇到比基准数小的数则停下来
            while (left < right && arr[right] >= flag) {
                right--;
            }

            // 4、left标兵从左向右移动，遇到大于基准数的数则停下来
            while (left < right && arr[left] <= flag) {
                left++;
            }

            //5、交换right和left数
            if (left < right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }

        // 6、若left和right重合，则把重合数与基准数进行交换
        arr[start] = arr[left];
        arr[left] = flag;

        // 8、对基准数左右两边的数组重复上述步骤，直至left和right重合。
        fastSort(arr, start, left - 1);
        fastSort(arr, left + 1, end);
    }
}
